//9:02PM-9:20PM-9:30PM
#include<iostream>
#include<set>
#include<vector>
#include<deque>
#include<utility>

using namespace std;

void allSubSet(vector<int>& is, vector<vector<int>>& subset) {
	for(int i=-1; i<(int)is.size(); i++) {
		if(i==-1) {
			vector<int> ts;
			subset.push_back(ts);
		} else {
			vector<vector<int>> tsubset;
			for(int j=0; j<subset.size(); j++) {
				vector<int> ts=subset[j];
				ts.push_back(is[i]);
				tsubset.push_back(ts);
			}
			subset.insert(subset.end(), tsubset.begin(), tsubset.end());
		}
	}
}

//10:07AM-10:11AM
int PossibleWays(int n) {
	if (n<0) return 0;
	if (n==0) return 1;
	vector<int> ways(n+1);
	ways[0]=1;
	ways[1]=1;
	ways[2]=2;
	ways[3]=3;
	for (int i=4; i<=n; i++) {
		ways[i]=ways[i-1]+ways[i-2]+ways[i-3];
	}
	return ways[n];
}

//10:30AM-
int RobotWays(int X, int Y, vector<vector<int>>& mem) {
	if (mem[X][Y]>=0) {
		return mem[X][Y];
	}

	int left, up;
	if(X>0) {
		left=RobotWays(X-1, Y, mem);
	} else {
		left=0;
	}

	if(Y>0) {
		up=RobotWays(X, Y-1, mem);
	} else {
		up=0;
	}
	
	mem[X][Y]=left+up;
	return left+up;
}

//find one path
//12:40PM-
bool RobotPath(int sX, int sY, int X, int Y, vector<vector<int>>& mem, deque<char>& s) {
	if(mem[sX][sY]<0) {
		cout<<"No feasible path"<<endl;
		return false;
	}
	if(sX==X && sY==Y) {
		return true;
	}

	bool b=false;
	if(sX<X && mem[sX+1][sY]>=0) {
		s.push_back('R');
		b=RobotPath(sX+1, sY, X, Y, mem, s);
		if(!b) {
			s.pop_back();
		}
	}

	if(!b) {
		s.push_back('D');
		if(sY<Y && mem[sX][sY+1]>=0) {
			b=RobotPath(sX, sY+1, X, Y, mem, s);
		}
	}

	if(!b) {
		mem[sX][sY]=-1;
	}

	return b;
}

//1:31PM-1:47PM
//assume exists, distinct
int findmagic(vector<int>& val, int begin, int end) {
	if(begin>end) {
		return -1;
	}
	int mid=(end+begin)/2;
	int count=0;
	if(val[mid]==mid) {
		return mid;
	} else if(val[mid]<mid) {
		return findmagic(val, mid+1, end);
	} else {
		return findmagic(val, begin, mid-1);
	}
}

int findmagicEx(vector<int>& val, int begin, int end) {
	if(begin>end && end >= val.size()) {
		return -1;
	}
	int mid=(end+begin)/2;
	int count=0;
	if(val[mid]==mid) {
		return mid;
	} else if(val[mid]<mid) {
		if(val[begin]==begin) {
			return begin;
		} else if (val[begin]<begin) {
			return findmagic(val, mid+1, end);
		} else {
			return findmagic(val, begin+1, mid-1);
		}
	} else {
		if(val[end]==end) {
			return end;
		} else if(val[end]>end) {
			return findmagic(val, begin, mid-1);
		} else {
			return findmagic(val, mid+1, end-1);
		}
	}
}

int main(int argc, char *argv[]) {
	//vector<int> a;
	//a.push_back(0);
	//a.push_back(1);
	//a.push_back(2);
	//a.push_back(3);

	//vector<vector<int>> as;
	//allSubSet(a, as);

	//for(int i=0; i<as.size(); i++) {
	//	if(as[i].empty()) {
	//		cout<<"@\t";
	//	} else {
	//		for(int j=0; j<as[i].size(); j++) {
	//			cout<<as[i][j]<<"\t";
	//		}
	//	}
	//	cout<<endl;
	//}

	vector<vector<int>> mem(6);
	for(int i=0; i<6; i++) {
		mem[i].resize(6, 0);
	}
	mem[1][1]=-1;
	mem[1][2]=-1;
	mem[2][1]=-1;
	mem[4][0]=-1;
	deque<char> s;
	//RobotPath(0, 0, 5, 5, mem, s);
	vector<int> a(11);
	a[0]=-10;
	a[1]=-5;
	a[2]=2;
	a[3]=2;
	a[4]=2;
	a[5]=2;
	a[6]=4;
	a[7]=7;
	a[8]=9;
	a[9]=12;
	a[10]=13;
	int d=findmagicEx(a, 0, 10);
}